package string;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * 91.复原ip地址
 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。

 示例:

 输入: "25525511135"
 输出: ["255.255.11.135", "255.255.111.35"]

 来源：力扣（LeetCode）
 链接：https://leetcode-cn.com/problems/restore-ip-addresses
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

 输出 0000
 */
public class Q93_RestoreIpAddresses {
    /**
     * 1.
     */
    private List<String> restoreIpAddresses1(String s) {
        List<String> cur = new ArrayList<>();
        List<String> res = new ArrayList<>();
        backtrack(s, 0, "", res, 4, s.length());
        return res;
    }
    private void backtrack(String s, int pos, String sb, List<String> res, int flag, int len) {
        if (s.length() > 12) {
            return;
        }
        if (flag < 0) {
            return;
        }
        if (flag == 0 && pos == len) {
            System.out.println(sb.substring(0 ,sb.length()-1));
            return;
        }
        for (int i=pos; i<pos+3; i++) {
            if (i < len) {
                // 0000
                if (pos == i && s.charAt(i)-'0' == 0) {
                    backtrack(s, i+1, sb+s.charAt(i)+".", res, flag-1, len);
                    break;
                }
                String seg = s.substring(pos, i+1);
                if (Integer.parseInt(seg) <= 255) {
                    backtrack(s, i+1, sb+seg+".", res, flag-1, len);
                }
            }
        }
    }

    /**
     * 2.
     */
    private List<String> restoreIpAddresses2(String s) {
        List<String> cur = new ArrayList<>();
        List<String> res = new ArrayList<>();
        backtrack(s, 0, cur, res);
        return res;
    }
    private void backtrack(String s, int pos, List<String> cur, List<String> res) {
        if (s.length() > 12) {
            return;
        }
        if (s.length() - pos > 3 * (4 - cur.size())) {
            return;
        }
        if (cur.size() > 4) {
            return;
        }
        int sLen = s.length();
        if (pos >= sLen && cur.size() == 4){
            String str = String.join(".", cur);
            res.add(str);
            return;
        }
        for (int i=1; i<=3; i++) {
            if (pos+i > sLen) {
                break;
            }
            String tmp = s.substring(pos, pos+i);
            if (tmp.startsWith("0") && tmp.length()>1 || Integer.parseInt(tmp) > 255) {
                break;
            }
            cur.add(tmp);
            backtrack(s, pos+i, cur, res);
            cur.remove(cur.size()-1);
        }
    }

    /**
     * 3.
     */
    private List<String> restoreIpAddresses3(String s) {
        List<String> ans = new ArrayList<>(); //保存最终的所有结果
        getAns(s, 0, new StringBuilder(), ans, 0);
        return ans;
    }
    /**
     * @param:  start 字符串开始部分
     * @param:  temp 已经划分的部分
     * @param:  ans 保存所有的解
     * @param:  count 当前已经加入了几部分
     */
    private void getAns(String s, int start, StringBuilder temp, List<String> ans, int count) {
        //如果剩余的长度大于剩下的部分都取 3 位数的长度，那么直接结束
        //例如 s = 121231312312, length = 12
        //当前 start = 1，count 等于 1
        //剩余字符串长度 11，剩余部分 4 - count = 3 部分，最多 3 * 3 是 9
        //所以一定是非法的，直接结束
        if (s.length() - start > 3 * (4 - count)) {
            return;
        }
        //当前刚好到达了末尾
        if (start == s.length()) {
            //当前刚好是 4 部分，将结果加入
            if (count == 4) {
                ans.add(new String(temp.substring(0, temp.length() - 1)));
            }
            return;
        }
        //当前超过末位，或者已经到达了 4 部分结束掉
        if (start > s.length() || count == 4) {
            return;
        }
        //保存的当前的解
        StringBuilder before = new StringBuilder(temp);

        //加入 1 位数
        temp.append(s.charAt(start) + "" + '.');

        getAns(s, start + 1, temp, ans, count + 1);

        //如果开头是 0，直接结束
        if (s.charAt(start) == '0')
            return;

        //加入 2 位数
        if (start + 1 < s.length()) {
            temp = new StringBuilder(before);//恢复为之前的解
            temp.append(s.substring(start, start + 2) + "" + '.');
            getAns(s, start + 2, temp, ans, count + 1);
        }

        //加入 3 位数
        if (start + 2 < s.length()) {
            temp = new StringBuilder(before);
            int num = Integer.parseInt(s.substring(start, start + 3));
            if (num >= 0 && num <= 255) {
                temp.append(s.substring(start, start + 3) + "" + '.');
                getAns(s, start + 3, temp, ans, count + 1);
            }
        }

    }


    public static void main(String[] args) {
        Q93_RestoreIpAddresses q93_restoreIpAddresses = new Q93_RestoreIpAddresses();
        List<String> list = q93_restoreIpAddresses.restoreIpAddresses1("0000");
        list.stream().forEach(str-> System.out.println(str));
        List<String> list1 = q93_restoreIpAddresses.restoreIpAddresses2("0000");
        list1.stream().forEach(str-> System.out.println(str));
    }
}